1. Field of Invention
This invention relates generally to content addressable memories and specifically to multiple match conditions in a content addressable memory.
2. Description of Related Art
A content addressable memory (CAM) includes an array of memory cells arranged in a matrix of rows and columns. Each memory cell stores a single bit of digital information. The bits stored in a row of memory cells in the CAM array constitute a CAM word. During compare operations, a comparand word is received at appropriate input terminals of the CAM and then compared to all the CAM words. If the comparand word matches one of the CAM words, a match line corresponding to the matching CAM word is asserted to indicate a match condition. If the comparand word matches more than one of the CAM words, the match line corresponding to each of the matching CAM words is asserted, and a "multiple match" flag is also asserted to indicate the multiple match condition.
The multiple match flag is generated in response to a logical combination of the match line signals. The complexity of multiple match circuits that implement this logical combination increases approximately exponentially with increases in the number of CAM words. For example, where a CAM array has only two words, the multiple match flag is generated by simply ANDing the two corresponding match signals. Thus, for an array having 2 CAM words, the multiple match flag=m0*m1, where m0 and m1 are the first and second corresponding match line signals, respectively, and * indicates the logical AND function. Here, the multiple match circuit is typically implemented using a single 2-input AND gate. For 4 CAM words, the multiple match flag MMF=m0*m1+m0*m2+m0*m3+m1*m2+m1*m3+m2*m3, where + indicates the logical OR function. The corresponding multiple match circuit is typically implemented using six 2-input AND gates and one 6-input OR gate to provide the multiple match flag MMF. In a similar manner, for an array having 8 CAM words, the multiple match circuit is typically implemented using twenty-eight 2-input AND gates and a 28-input OR gate. Therefore, as shown in the above example, the size and complexity of the multiple match logic circuit is approximately exponentially related to the number of CAM words, as there is an AND gate for each possible combination of match line signals.
The rapid growth of the Internet has resulted in an explosion in the number of Internet Protocol (IP) addresses which, in turn, has necessitated the use of increasingly larger CAM arrays for IP address routing. Since the size and complexity of conventional multiple match circuits are approximately exponentially related to the number of CAM words, as described above, incremental increases in CAM array size typically result in approximately exponential increases in the size and complexity of the associated multiple match circuit. This exponential relationship between number of CAM words and size of the multiple match circuit can undesirably limit the cost-effectiveness of larger CAM array sizes desired for IP addressing.